#include<iostream>
using namespace std;
const int N = 2010;
const int mod = 1e8;
int f[N][N];
int r[N];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		cin >> r[i];
	}
	f[0][0] = 1;//不给初始化所有值都是0
	for (int i = 1;i <= n;i++)
	{
		//从左往右填
		for (int j = 0;j < m;j++)//特别注意这个地方不能等于m，因为实际上我们第二个坐标表示的模完m之后的值取不到m
		{
			//f表示的是实力模完m后的这个地方在前i个挑选出来的最大的方案数
			//这个题必须得都加到一起之后再模，不然你很有可能凑出他那个模数m，然实际上这个是出现不了的，应该是才对
			//选
			//因为是方案数，直接加等就行
			f[i][j] += (f[i - 1][j] + f[i - 1][((j - r[i] % m) % m + m) % m]) % mod;//因为有可能是负数，所以得取正
			//取正操作实际上也会模，所以说不用担心超了
		}
	}
	//注意是f[n][0]才是正好整除的时候
	//-1是因为我们得把得把什么也不选的f[0][0]删去。
	//我们在加的过程中肯定是把f[0][0]加进去了，比如说进入循环的第一步
	//但是我们f[0][0]实际上是什么也不选，如果真的加上他了那就加多了。
	cout << f[n][0] - 1 << endl;
	return 0;
}